/**
 * @Auther: MFM
 * @Date: 2022/3/12 - 03 - 12 - 17:45
 * @version: 1.0
 */

public class LinkedDemo<E> {
    /*
     * 链表
     * 属性：(前驱 元素 后继) 头节点 当前节点 实际数量 是否为空
     * 方法：增（头，尾，任意）删改查
     * */

    private class Node<E> {
        //元素
        private E e;
        //前驱
        private Node Pre;
        //后继
        private Node Next;


        public Node(E e, Node pre, Node next) {
            this.e = e;
            Pre = pre;
            Next = next;
        }

        //初始化只有一个节点 前后都为null
        public Node() {
            this(null, null, null);
        }

        public Node(E e) {
            this(e, null, null);
        }

        public Node(E e, Node next) {
            this(e, null, next);
        }

        @Override
        public String toString() {
            StringBuilder sb = new StringBuilder();
            sb.append("Node:E=" + e + ",Pre=" + Pre + ",Next=" + Next);
            return sb.toString();
        }
    }

    //实际数量
    private int size;

    //头节点
    private Node head;

    //当前节点
    private Node node;

    public LinkedDemo() {
        head = null;
        size = 0;
    }

    public LinkedDemo(Node head) {
        this.head = head;
        size = 0;
    }

    //增
    //增加到任意位置
    public void add(E e, int index) throws Exception {
        if (index < 0) {
            throw new Exception("索引错误");
        }


        Node<E> newNode = new Node<>(e);

        if (head == null) {
            //如果没有头节点（原链表没有节点）
            head = new Node<>(e);
            node = head;
            return;
        }
        //index大于size时 直接将node放到链表最后
        if (index>size){
            addLast(e);
        }

        //当index为尾时
        if (index==size){
            node = head;
            for (int i = 0; i < index; i++) {
                node = node.Next;
            }
            node.Next = newNode;
            newNode.Pre = node;

        }

        //将现在的节点node设置成头节点head
        node = head;
        for (int i = 0; i < index; i++) {
            node = node.Next;
        }

        //将index-1的节点的next赋予newNode newNode 的next就是node的next
        newNode.Next = node.Next;

        //将node.Next的Pre改成newNode
        node.Next.Pre = newNode;

        //再将node的next换成newNode 现在数据结构就是 node->newNode<->node.next
        node.Next = newNode;

        //再将newNode的前驱变为node
        newNode.Pre = node;

        //增加完毕
        size++;
    }

    //增加头部
    public void addFirst(E e) throws Exception {
        if (head==null){
            head = new Node(e);
            return;
        }

        node = head;

        head = new Node(e);

        head.Next = node;

        node.Pre = head;

        size++;

    }

    //增加尾部
    public void addLast(E e) throws Exception {
        if (head==null){
            head = new Node(e);
            return;
        }

        node = head;

        for (int i = 0; i < size; i++) {
            node = node.Next;
        }

        Node newNode = new Node(e);

        node.Next = newNode;
        newNode.Pre = node;

        size++;
    }


    //删
    //根据索引删除node
    public E delete(int index)throws Exception{
        if (head==null){
            throw new Exception("链表内无内容无法删除");
        }

        node = head;

        for (int i = 0; i < index; i++) {
            node = node.Next;
        }

        //记录要删除的节点的值
        E e = (E)node.e;

        //如果删除的节点是头节点
        if (index==0){
            node.Next.Pre =null;
            node = node.Next;
            return e;
        }

        //node为将要删除的节点 将该节点的Pre的Next转为该节点的Next即可删除该节点
        node.Pre.Next = node.Next;

        return e;
    }

    //根据元素删除node
    public E delete(E e) throws Exception {
        if (head==null){
            throw new Exception("链表内无内容无法删除");
        }

        node = head;

        for (int i = 0; i < size; i++) {
            if (node.e.equals(e)){
                delete(i);
                return e;
            }
            node = node.Next;
        }

        //返回null表示没有找到该内容
        return null;
    }

    //改
    //根据索引修改
    public E set(int index,E e) throws Exception {
        if (head==null){
            throw new Exception("链表内无内容无法修改");
        }

        node = head;

        for (int i = 0; i < index; i++) {
            node = node.Next;
        }

        node.e = e;

        return e;
    }

    //查
    //根据索引查找
    public E find(int index) throws Exception {
        if (head==null){
            throw new Exception("链表内无内容无法删除");
        }

        //当index大于size时 直接报错
        if (index>size){
            throw new Exception("该索引无节点");
        }

        node = head;

        for (int i = 0; i < index; i++) {
            node = node.Next;
        }


        return (E) node.e;
    }

    //根据元素查索引
    public int find(E e) throws Exception {
        if (head==null){
            throw new Exception("链表内无内容无法删除");
        }

        node = head;

        for (int i = 0; i < size; i++) {
            if (e.equals(node.e)){
                return i;
            }
            node = node.Next;
        }
        return -1;
    }

    //遍历所有链表节点的元素
    public void findAll() throws Exception{
        if (head==null){
            throw new Exception("链表内无内容无法遍历");
        }

        node = head;

        System.out.print(node.e.toString()+" ");

        for (int i = 0; i < size; i++) {
            node = node.Next;
            System.out.print(node.e.toString()+" ");
        }
        System.out.println();
    }

    public int getSize(){
        return size;
    }

    public boolean isEmpty(){
        return size==0;
    }

    @Override
    public String toString() {
        return super.toString();
    }
}
